package com.lw.leetcode.back.c;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 面试题 04.09. 二叉搜索树序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/22 9:40
 */
public class BSTSequences {

    private List<List<Integer>> all = new ArrayList<>();

    public List<List<Integer>> BSTSequences(TreeNode root) {
        if (root == null) {
            all.add(new ArrayList<>());
            return all;
        }
        List<Integer> items = new ArrayList<>();
        List<TreeNode> queue = new ArrayList<>();
        queue.add(root);
        find(items, queue);
        return all;
    }

    private void find(List<Integer> items, List<TreeNode> queue) {
        int size = queue.size();
        if (size == 0) {
            all.add(items);
        }
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.get(i);
            ArrayList<Integer> items2 = new ArrayList<>(items);
            items2.add(node.val);
            ArrayList<TreeNode> queue2 = new ArrayList<>(queue);
            queue2.remove(i);
            if (node.left != null) {
                queue2.add(node.left);
            }
            if (node.right != null) {
                queue2.add(node.right);
            }
            find(items2, queue2);
        }
    }

}
